/*
 * Algorithms.java
 *
 * Created on August 15, 2007, 11:59 AM
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

package edu.psu.bd.math.grooms;

import java.util.HashSet;
import java.util.Set;
import org.cgsuite.util.Grid;

/**
 *
 * @author jfp149
 */
public final class Algorithms {
    
    /** Creates a new instance of Algorithms */
    private Algorithms() {
    }
    
    public static int manhattanDistance(int x1, int y1, int x2, int y2) {
        return Math.abs(x1-x2) + Math.abs(y1-y2);
    }
    
    public static void incrementAt(
            org.cgsuite.util.Grid g, int row, int col) {
        int newValue = g.getAt(row,col)+1;
        if (newValue == 256) {
            throw new ArithmeticException();
        }
        g.putAt(row,col,newValue);
        
    }
    
    public static int sumGrid(org.cgsuite.util.Grid g) {
        int sum = 0;
        for (int row = 0; row < g.getNumRows(); row++) {
            for (int col = 0; col < g.getNumColumns(); col++) {
                sum += g.getAt(row,col);
            }
        }
        return sum;
    }
    
    public static org.cgsuite.util.Grid trimGrid(org.cgsuite.util.Grid g) {
        
        //if (g.getNumRows() == 1)
        //  return g;
        if (sumGrid(g.subgrid(
                g.getNumRows()-1,
                g.getNumRows(),
                0,g.getNumColumns()))
                == 0) {
            return trimGrid(
                    g.subgrid(0,g.getNumRows()-1,0,g.getNumColumns()));
        }
        return g;
        
    }
    
    public static String toString(org.cgsuite.util.Grid g) {
        StringBuffer sb = new StringBuffer();
        sb.append("Liberties\n4 3 2 1 \n---------\n");
        for (int row = 0; row < g.getNumRows(); row++) {
            sb.append(Integer.toString(row + 1));
            sb.append("| ");
            for (int col = g.getNumColumns()-1; col >= 0 ; col--) {
                sb.append(Integer.toString(g.getAt(row,col)));
                sb.append(' ');
            }
            sb.append('\n');
            
        }
        
        sb.append("^ ---------\n|          \nDistance   ");
        return sb.toString();
    }
    
    private static void floodLoop(org.cgsuite.util.Grid grid,
            int row,
            int col,
            int fill,
            int old) {
        int fillL, fillR;
        boolean in_line=true;
        
        
        
        
        
        // find left side, filling along the way
        fillL = fillR = row;
        while(in_line) {
            int p = grid.getAt(fillL,col);
            grid.putAt(fillL,col,fill);
            fillL--;
            in_line = (fillL < 0) ? false : (grid.getAt(fillL,col) == old);
        }
        
        fillL++;
        
        // find right side, filling along the way
        in_line = true;
        while (in_line) {
            grid.putAt(fillR,col,fill);
            fillR++;
            in_line = (fillR > grid.getNumRows()-1) ? false :
                (grid.getAt(fillR,col) == old);
        }
        
        fillR--;
        
        // look up and down
        for(int i=fillL; i<=fillR; i++ ) {
            if ( col>0 && grid.getAt(i,col-1) == old)
                floodLoop(grid,i,col-1,fill,old);
            if ( col<grid.getNumColumns()-1 && (grid.getAt(i,col+1) == old))
                floodLoop(grid,i,col+1,fill,old);
        }
        
        
    }
    
    // Initial method you must call
    public static void floodLoop(org.cgsuite.util.Grid grid,
            int row,
            int col,
            int value) {
        
        
        // validation so we don't fall in an infinite loop trying to
        // paint in the same color
        if ( grid.getAt(row,col) == value )
            return;
        
        floodLoop(grid,row,col,value,grid.getAt(row,col) );
    }
    
    public static Chain getChain(Grid grid,
            int row, int col) {
        Grid stones = getChainPoints(grid.clone(),row,col);
        
        Grid liberties = new org.cgsuite.util.Grid(
                grid.getNumRows(),
                grid.getNumColumns(),
                org.cgsuite.util.Grid.BitsPerEntry.ONE);
        for (int r = 0; r < stones.getNumRows(); r++) {
            for (int c = 0; c < stones.getNumColumns(); c++) {
                if (stones.getAt(r,c)!=1)
                    continue;
                
                for (org.cgsuite.util.Grid.Direction point :
                    org.cgsuite.util.Grid.Direction.ORTHOGONALS) {
                        if (!grid.isValidShift(r,c,point,1))
                            continue;
                        if (grid.getAt(
                                r+point.rowShift(1),c+point.columnShift(1))
                                == GoRoom.EMPTY) {
                            liberties.putAt(
                                    r+point.rowShift(1),
                                    c+point.columnShift(1),
                                    1);
                        }
                    }
            }
        }
        
        return new Chain(stones, liberties);
    }
    
    private static org.cgsuite.util.Grid getChainPoints(
            Grid b, int row, int col) {
        Grid stones = new Grid(
                b.getNumRows(),
                b.getNumColumns(),
                Grid.BitsPerEntry.ONE);
        stones.putAt(row,col,1);
        
        int myColor = b.getAt(row,col);
        int floodfillColor = GoRoom.getInverse(myColor);
        b.putAt(row, col,floodfillColor);
        
        
        for (org.cgsuite.util.Grid.Direction neighbor :
            org.cgsuite.util.Grid.Direction.ORTHOGONALS) {
                if (!b.isValidShift(row,col,neighbor,1))
                    continue;
                
                if (b.getAt(row+neighbor.rowShift(1),
                        col+neighbor.columnShift(1)) == myColor) {
                    if (!contains(stones, row+neighbor.rowShift(1),
                            col+neighbor.columnShift(1))) {
                        addAll(stones,getChainPoints(b,
                                row+neighbor.rowShift(1),
                                col+neighbor.columnShift(1)));
                    }
                }
            }
            
            return stones;
    }
    
    public static void addAll(org.cgsuite.util.Grid a,
            org.cgsuite.util.Grid b) {
        checkDimensions(a,b);
        for (int row = 0; row < a.getNumRows(); row++) {
            for (int col = 0; col < a.getNumColumns(); col++) {
                if (b.getAt(row,col) == 1)
                    a.putAt(row,col,1);
            }
        }
    }
    
    private static void checkDimensions (org.cgsuite.util.Grid a,
            org.cgsuite.util.Grid b) {
        if (a.getNumRows() != b.getNumRows() ||
                a.getNumColumns() != b.getNumColumns())
            throw  new IllegalArgumentException("Grid Dimension Mismatch");
    }
    
    public static void removeAll(org.cgsuite.util.Grid a,
            org.cgsuite.util.Grid b) {
        checkDimensions (a,b);
        for (int row = 0; row < a.getNumRows(); row++) {
            for (int col = 0; col < a.getNumColumns(); col++) {
                if (b.getAt(row,col) == 1) {
                    a.putAt(row,col,0);
                }
            }
        }
    }
    
    public static boolean containsAll(org.cgsuite.util.Grid a,
            org.cgsuite.util.Grid b) {
        checkDimensions(a,b);
        for (int row = 0; row < a.getNumRows(); row++) {
            for (int col = 0; col < a.getNumColumns(); col++) {
                if (a.getAt(row,col) == 1
                        && 1 == b.getAt(row,col))
                    return true;
            }
        }
        return false;
    }
    
    private static boolean contains(
            org.cgsuite.util.Grid grid, int row, int col) {
        return grid.getAt(row,col) == 1;
    }
    
    public static long factorial(long n) {
        if      (n <  0) throw new RuntimeException("Underflow error in factorial");
        else if (n > 20) throw new RuntimeException("Overflow error in factorial");
        else if (n == 0) return 1;
        else             return n * factorial(n-1);
    }

    
    
}
